import functools
class Solution:
    """
    自上向下
    """
    def minPathSum(self, grid) -> int:
        if not grid and not grid[0]:
            return 0

        rows, columns = len(grid), len(grid[0])

        @functools.lru_cache
        def __dfs(row, column):
            if row == rows-1 and column == columns-1:
                return grid[-1][-1]

            if row >= rows or column >= columns:
                return float('inf')

            return grid[row][column] + min(__dfs(row+1, column), __dfs(row, column+1))
        
        return __dfs(0, 0)



if __name__ == '__main__':
    s = Solution()
    grid = [[1,3,1],[1,5,1],[4,2,1]]
    print(s.minPathSum(grid))
    